1. Field of the Invention
The present invention generally relates to computer implemented structures for processing multiple asynchronous protocols, and in particular to use of such structures to more efficiently multiplex communications in a data network connecting multiple sets of asynchronous devices with host computers.
2. Description of the Prior Art
Advances in communications technology are continuing to provide improved physical linkages wherein distributed devices having their own intelligence are able to be connected together in a coordinated system. It is characteristic of such systems that the distributed devices are independent and asynchronous, i.e. they initiate activity on their own and at times which are not determined or controlled by other devices connected to the system or by intelligence associated with the system itself. Hereinafter the term "asynchronous" will be used to refer to such devices, and the term "system" will be used to refer to the collective entity comprising such devices and the logic according to which the coordination of such devices is effected.
The present invention is an improvement in the technology for connecting such devices. The improvement was developed in conjunction with a particular class of systems of such devices, and the description hereinafter of the best mode of practicing the invention refers to specific technology usable with that particular class of systems. However, as will be evident from the description, the invention may be practiced with other classes of systems and with other devices than those used for illustration herein. In particular, as is common with technology implemented using computer software, the term "asynchronous device" as used herein may refer not only to elemental hardware terminals such as bar code readers but also to entire "systems" which may be connected together in a broader "system" through practice of the invention.
Connectivity technology, as addressed in this application, responds to requirements of both asynchronous devices and the system logic according to which the coordination of such devices is effected. It is characteristic of such systems that both timing and sequencing are important requirements. For example, effective use of an asynchronous device for a particular purpose may require a response from the system or from another device on the system within one second. Or a response may be required within ten seconds, or within ten milliseconds, or within ten microseconds. System logic may involve a complex sequence of such response requirements, linking multiple devices within the system.
The multiplicity of asynchronous devices within such systems requires a strategy for handling contention between the devices for system resources. Scheduling and coordination within such systems require a methodology for allowing multiple paths which are concurrent in accordance with system logic to proceed essentially in parallel. To the extent that such systems are implemented using computer software technology rather than special purpose circuitry, it is common to simulate concurrency by organizing system resources (typically a single processor) into small work pieces which are allocated successively among logically concurrent tasks. The work pieces are small enough, e.g. ten milliseconds, that system logic cannot readily discern that the execution of parallel tasks are other than concurrent.
For the purposes of this application, in accordance with conventional terminology for multi-tasking operating systems, the term "process" when employed as a noun will be used to refer to the smallest unit of computer implemented structure which may be assigned a unit or "work piece" of computer processing resources. The noun "process" is to be distinguished from the verb "to process", notwithstanding that a "process" may do "processing" and may consume "processing" resources. It should be noted that an application program may be structured as a single process, and "multi-tasking" often refers in practice to time sharing among multiple application programs each of which is a single process. In general, however, a computer implementation of a single apparatus or method within a multi-tasking environment may be accomplished by constructing multiple tasks or processes. Processes are to be distinguished from "procedures" or "routines", which are also elements of structure for computer implementation of an apparatus or a method. A single process may encompass many subordinate structures, such as procedures or routines. The design and interconnection of these structures admits of enormous variety.
Scheduling and coordination within a system of asynchronous devices requires a methodology for allowing communication between logically related tasks or processes. In software implementations it is common to use semaphores, shared memory and mailboxes to accomplish this communication. For a discussion of relevant prior art see chapter on "Real Time Design" in Software Engineering by Roger S. Pressman (McGraw-Hill, 1987) and citations therein. The present invention includes concepts taken from this existing technology.
Practical implementations of systems of asynchronous devices within the prior art are often difficult. This is so in part because operating systems which are adapted to the requirements of such systems may not be available. Theoretically, it is possible to develop an implementation without the benefit of services provided by an existing operating system. However, this approach is not always practical, not only because of cost considerations but also because of reliability considerations. Systems of asynchronous devices typically require that processing resources be shared among tasks which must be executed at more or less the same time in order to comply with system logic requirements. While multi-tasking operating systems which address these requirements are old in the art, new implementations of this prior art typically require a significant period of development and testing before a suitable degree of reliability is achieved.
Consequently, there are substantial practical advantages to implementations which build upon the services provided by existing operating systems. Such a "building block" approach is characteristic of computer software implementations; operating systems themselves reflect this approach.
A further reflection of this "building block" approach is what are called "device drivers" which connect device electronics to computer software implementations. Typically, device manufacturers (who are most knowledgable about the electrical characteristics of their devices) provide software which is loaded into the operating system and which is then available for use by any computer software implementation which needs access to the device. This approach is advantageous because the computer software implementation can use the standard input/output services of the operating system to communicate with the device. As viewed by the computer software implementation, device drivers constructed in conformity with these services allow simpler and more cost effective access to the respective devices.
In some cases the manufacturer (or a third party provider) may provide not only a device driver which is loaded into the operating system but also additional software modules (commonly called an "application program interface" or API) for inclusion in the computer software implementation and which the computer software implementation then uses to access the device driver and thence the device. This approach may be taken when an operating system's standard input/output services are not adequate to take full advantage of the device's capabilities.
For the purposes of this application the term "device driver" will be used to refer to both device drivers and APIs, however they may be combined to provide to the computer software implementation with a means of access to the device.
Systems of asynchronous devices may be implemented using two broad classes of operating systems. There exist some operating systems which are designed specifically for such applications. Examples of these are Intel's real-time iRMX system, Motorola's Regulus system, and QNX by Quantum Software Systems, Ltd. Note that iRMX uses the "mailbox" technology referred to earlier. QNX also uses similar technology, not simply to provide for communication between application processes but also to handle communication between operating system processes. However, use of these systems to implement the present invention is not economical because there is not a base of readily available device drivers and communication protocols adapted for these systems.
A second class of operating systems used for implementing systems of asynchronous devices are general purpose systems that have been enhanced to provide the required services. Typical enhancements for real-time systems include provision of mechanisms for multiple levels of priority and memory locking. Context switching time and interrupt latency are often critical factors in determining whether an existing operating system is viable for a particular real-time application. See Pressman, op. cit. at pp. 372-373.
In common parlance, "real-time" refers to systems whose logic is largely implemented by interrupts and context switches, because processor speed is not fast enough--relative to time response requirements of system logic--to support a software implementation. These systems are not in general amenable to implementation using the present invention, although complex systems which include isolatable "real-time" components, where communication between such components and the remainder of the system is governed by a logic whose response time requirements are much slower relative to processor speed, could use the present invention for this relatively slower logic. Within current processor technology, such relatively slower logic would have response time requirements in the range of a few hundredths of a second to a second.
In addition to the practical advantage of being able to build upon services already developed--an advantage applicable to both operating systems developed specifically for asynchronous applications and general purpose operating systems--general purpose operating systems also provide portability and flexibility advantages. These are particularly important in commercial applications where it is desirable to integrate a system of asynchronous devices into an existing data processing environment, i.e. where one or more of the system's "asynchronous devices" is an existing host computer. Commonly, such integration requires communications drivers (e.g. for TCP/IP, SNA, X.25, 3270 protocols and the like), which are readily available for general purpose operating systems but which would have to be developed for special purpose operating systems.
UNIX is an existing operating system with these portability and flexibility advantages. UNIX is a multitasking operating system, which shares the time of the central processor among multiple tasks or processes. The operating system maintains a list of active processes, and passes control to the process having the highest priority. Each entry on the list contains a flag for indicating that the process is waiting for another process to complete. If this flag has been set, the process is "asleep" and control is not passed to such a process, even when it has priority, until after the referenced process completes. This feature--common to multitasking operating systems--avoids waste of processor resources. After a process obtains control, that control is passed back to the operating system when the process completes or when the process uses up the time slice (typically ten milliseconds) which has been allocated to it by the operating system. If the process completed, the operating system resets the flag of any process in the list which was waiting on completion of that process. Any process whose flag has been reset in this manner is "awake" and ready to be assigned control. The operating system then recalculates priorities according to an algorithm, and assigns control to the highest priority process.
Of particular significance for practicing the present invention is the streams facility added with Release 5.3 of AT&T's System V version of UNIX. Usually, communications drivers (and device drivers in general) are loaded into the UNIX kernel at boot time. Streams provides a mechanism for allowing an application to adapt communication drivers "on the fly" without having to reboot the system. In addition, use of streams requires applications to use a simple interface which is uniform across all device drivers which are within the streams facility. In part because of this simplicity and uniformity, device manufacturers are providing streams drivers for their devices.
Streams is an addition to the AT&T version of UNIX. Prior to the introduction of streams, the Berkely implementation of UNIX had introduced a similar but less flexible and less accessible facility called "sockets" which permitted two processes to communicate using the same file descriptor for both reads and writes. The socket facility is based upon the UNIX pipe.
Data transmission systems which include remote data gathering units such as bar code readers demonstrate the practical difficulty of implementing systems of asynchronous devices using prior art. U.S. Pat. No. 5,029,183 to Tymes describes such a system. In this system data packets are sent from remote units to intermediate base stations by means of a radio frequency (RF) link, and then forwarded to a central computer by means of a serial link. The system requires communication of relatively small amounts of data. While the Tymes patent describes the system, it leaves implementation to the prior art. Prior art does not teach how to implement the system so that response times are acceptable when there are more than a small number of remote terminals on the system.
The patent holder, Symbol Technologies, has not been able to overcome this limitation despite diligent and extensive efforts over a period of several years since issuance of the Tymes patent. Other competitors, with differently designed systems for the same market, have experienced comparable difficulties attempting to implement a system of asynchronous devices. Using prior art, system performance degrades unacceptably when there are more than a small number of remote terminals on the system.